// 283 移动零
// https://leetcode.cn/problems/move-zeroes/
#include<vector>
using namespace std;

class Solution
{
public:
    void moveZeroes(vector<int> &nums)
    {
        int prev = 0;
        int cur = 0;
        while (cur < nums.size())
        {
            if (nums[cur] != 0) // cur指向不为0
            {
                swap(nums[prev], nums[cur]);
                prev++;
            }
            else // cur指向为0
            {
                while (prev < nums.size() && nums[prev] == 0)
                {
                    prev++;
                }
                if (prev >= nums.size())
                {
                    return;
                }
                swap(nums[prev], nums[cur]);
            }
            cur++;
        }
    }
};

// 1089 复写0
// https://leetcode.cn/problems/duplicate-zeros/

class Solution
{
public:
    void duplicateZeros(vector<int> &arr)
    {
        // 1、找到cur和dest
        int cur = 0, dest = -1;
        while (dest < (int)(arr.size() - 1))
        {
            if (arr[cur] != 0)
            {
                dest++;
            }
            else
            {
                dest += 2;
            }
            cur++;
        }
        cur--;
        // cout<<cur<<endl;
        // cout<<dest<<endl;
        // 2、进行边界处理
        if (dest >= arr.size())
        {
            arr[dest - 1] = 0;
            dest -= 2;
            cur--;
        }
        // cout<<arr[cur]<<endl;
        // cout<<arr[dest]<<endl;
        // 3、进行复写
        while (cur >= 0)
        {
            if (arr[cur] != 0)
            {
                arr[dest] = arr[cur];
                dest--;
                cur--;
            }
            else
            {
                arr[dest] = arr[cur];
                arr[dest - 1] = arr[cur];
                cur--;
                dest -= 2;
            }
        }
    }
};


//202. 快乐数
//https://leetcode.cn/problems/happy-number/

class Solution {
public:
    int product(int num)
    {
        int res=0;
        while(num)
        {
            res+=(num%10)*(num%10);
            num=num/10;
        }
        return res;
    }
    bool isHappy(int n) 
    {
        //采用鸽巢结论，证明一定会无限循环
        //画图：可知类比判断链表是否有环
        //采用快慢指针,相遇一定是在环内，判断环内的数是否为1
        int slow=n;
        int fast=n;
        int count=0;
        do
        {
            slow=product(slow);
            fast=product(fast);
            fast=product(fast);
        }while(slow!=fast);
        if(slow==1)
        return true;
        return false;

    }
};

// 11. 盛最多水的容器
// https://leetcode.cn/problems/container-with-most-water/

//判断移动长板和短板
class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int left=0;
        int right=height.size()-1;
        int max=0;
        while(left<=right)
        {
            int shorter=height[left]<height[right]?height[left]:height[right];
            int volume=(right-left)*shorter;
            if(max<volume)
            {
                max=volume;
            }
            if(height[left]<height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return max;

    }
};

//611.有效三角形的个数
// https://leetcode.cn/problems/valid-triangle-number/


//1、先进行排序
//2、确定第三边，使用双指针
#include<algorithm>
class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        if(nums.size()<=2)
        {
            return 0;
        }
        sort(nums.begin(),nums.end(),[](const int a,const int b ){return a<b;});
        int cur=nums.size()-1;
        int left=0;
        int right=cur-1;
        int count=0;
        while(cur>=2)
        {
            while(left<right)
            {
                if(nums[left]+nums[right]>nums[cur])
                {
                    count+=right-left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
            cur--;
            left=0;
            right=cur-1;
        }
        return count;
    }
};

// 剑指 Offer 57. 和为s的两个数字
// https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        int left=0;
        int right=nums.size()-1;
        vector<int> ans;
        while(left<right)
        {
            if(nums[left]+nums[right]>target)
            {
                right--;
            }
            else if(nums[left]+nums[right]<target)
            {
                left++;
            }
            else
            {
                ans.push_back(nums[left]);
                ans.push_back(nums[right]);
                break;
            }
        }
        return ans;
    }
};

